import java.util.*;

/**
 * Created With IntelliJ IDEA
 * Description:牛客网:BM46 最小的K个数
 * <a href="https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=295&tqId=23263&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2023-03-09
 * Time: 18:30
 */
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        //建立大根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //先将前k元素入堆
        for (int i = 0; i < k; i++) {
            heap.add(input[i]);
        }
        //将后续元素入堆,并且弹出堆顶元素
        for (int i = k; i < input.length; i++) {
            heap.add(input[i]);
            heap.poll();
        }
        return new ArrayList<>(heap);
    }
}